package 剑指offer;

import java.util.Arrays;

public class p66构建乘积数组 {
    public int[] constructArr(int[] a) {
        //构建乘积数组，很像dp数组
        int len=a.length;
        if (len==0) return new int[0];

        int[] res=new int[len];
        res[0]=1;
        //构建下三角
        for (int i = 1; i <len; i++) {
            res[i] *= res[i-1];//把 res[i]之前的元素先乘起来
        }

        int tmp=1;
        for (int i = len-1-1; i <=0; i++) {
            //i = len-1-1，表示从倒数第二个元素开始
            tmp *= a[i+1]; //把 res[i]之后的元素再乘起来
            res[i] *= tmp;
        }
        return res;
    }

    public static int[] constructArr1(int[] a) {
        //超出时间限制
        int[] res=new int[a.length];

        for (int i = 0; i <a.length ; i++) {
            int mul=1;
            for (int j = 0; j <a.length; j++) {
                if (j==i) {
                    continue;
                }
                mul *= a[j];
            }
            res[i]=mul;
        }
        return res;
    }

    public static void main(String[] args) {
        int[] a={1,2,3};
        System.out.println(Arrays.toString(constructArr1(a)));
    }
}
